package mapset;

import java.util.*;


class Student implements Comparable<Student>{

    @Override
    public int compareTo(Student o) {
        return 0;
    }
}

public class Test {
    // 注意：Map有值 Set无值  Hash高效
    // 给题
    // 1.删重/去重：相关优先考虑Set
    private static void removeRepeat(int[] arr) {
        // 直接使用HashSet进行去重，当然也可以使用TreeSet，但是使用HashSet更加高效
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < arr.length; i++) {
            set.add(arr[i]);
        }
        System.out.println(set);
    }
    // 2.找到第一个重复数据
    // 使用HashSet且放入时进行检查！
    private static int findFirstRepeat(int[] arr) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < arr.length; i++) {
            if(!set.contains(arr[i])) {
                // 不在就进行add
                set.add(arr[i]);
            } else {
                return arr[i];
            }
        }
        return -1; // 就是没有重复的数据
    }
    // 3.统计词频：HashMap比较快（词频就需要Map）
    // key是当前数据，value就是出现的次数
    private static void count(int[] arr) {
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            int key = arr[i];
            // 看map中是否已经存在该元素，存在则value++，不存在则放入置1
            if(map.get(key) == null) {
                // 不存在
                map.put(key,1);
            } else {
                // 注意这里的写法
                // 已经存在，则value++
                int val = map.get(key); // 获取到当前key出现的次数
                map.put(key,val+1); // 进行了覆盖/更新
            }
        }
        System.out.println(map);
    }

    public static void main(String[] args) {
        int[] arr = new int[10_0000];
        // 随机生成可重复数据
        Random random = new Random();
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(5_0000);
        }
        System.out.println("去重：");
        removeRepeat(arr);
        System.out.println("第一个重复数据：");
        System.out.println(findFirstRepeat(arr));
        System.out.println("统计词频：");
        count(arr);
    }

    // TreeSet使用示例：
    public static void main5(String[] args) {
        Set<String> set = new TreeSet<>();
        set.add("lalala");
        set.add("lalala");
        set.add("lalala");
        set.add("babe");
        System.out.println(set); // 也是可以直接输出，重写了toString方法
    }

    // HashMap使用示例：
    public static void main4(String[] args) {
        // HashMap底层是哈希表，哈希表的插入时不需要比较大小
        Map<String,Integer> map = new HashMap<>();
        // 调用方法：底层是哈希表（统计词频）
        map.put("hustle",8);
        map.put("come on",2);
        map.put("hustle",6); // key值一样，直接替换/覆盖之前的数据
        map.put(null,1);
        // HashMap中key、value都可以存储null
        map.put(null,null);
        System.out.println(map); // 可以直接输出，说明重写了toString方法
        // 打印时，并不是有序的，也并不是按照存储元素的顺序进行打印的，也不会按照大小顺序去存储元素。


        // 把每一组数据分别进行打包（相当于数据变成类型）
        Set<Map.Entry<String,Integer>> entrySet = map.entrySet();
        // Entry 出现了红黑树，它有getKey/getValue方法
        for (Map.Entry<String,Integer> entry : entrySet)  {
            System.out.println("key:"+entry.getKey() + " value:"+entry.getValue());
        }
    }

    // TreeMap使用示例：
    public static void main3(String[] args) {
        // TreeMap底层是搜索树，搜索树的插入时需要比较大小的（通过key来比较大小的）
        Map<String,Integer> map = new TreeMap<>();
        // 调用方法：底层是红黑树（统计词频）
        map.put("hustle",8);
        map.put("come on",2);
        map.put("hustle",6); // key值一样，直接替换之前的数据
        System.out.println(map); // 可以直接输出，说明重写了toString方法
        // 注意输出顺序与插入顺序并不一致，因为搜索树是经过排序的

        // 把每一组数据分别进行打包（相当于数据变成类型）
        Set<Map.Entry<String,Integer>> entrySet = map.entrySet();
        // Entry 出现了红黑树，它有getKey/getValue方法
        for (Map.Entry<String,Integer> entry : entrySet)  {
            System.out.println("key:"+entry.getKey() + " value:"+entry.getValue());
        }

        // 返回所有value的可重复！！合集
        // 注意：可重复的意思是：不同key的value值可以重复，但是相同key只会存在最后一个！！（也就是：只会输出一次相同key）
        Collection<Integer> collection = map.values();
        System.out.println(collection);
        // collection是最高接口，但是一般使用向上转型而不是向下转型

        // 返回所有不重复！！的key合集:
        Set<String> set = map.keySet();
        System.out.println(set); // 注意也是可以直接进行输出！


        System.out.println(map.get("come on")); //根据key值来输出频率
        System.out.println(map.get("hello")); // 如果没找到就返回null
        System.out.println(map.getOrDefault("come on",12));
        // 就是说如果key的数据在之前就已经给定，即使再给默认值也是只会输出之前的频率数据
        // 但是如果是之前未出现过的key值就输出现在给定的默认值

        Map<Student,Integer> map2 = new TreeMap<>();
        // 实现TreeMap，则Student要可以比较，实现可比较接口
        map2.put(new Student(),2);

    }

    public static void main2(String[] args) {
        // Map是一个接口，是不能实例化接口的;要new一个具体的实现类。
        Map<String,Integer> map = new TreeMap<>(); // TreeMap底层是一棵红黑树，必须导入包
        Map<String,Integer> map2 = new HashMap<>(); // HashMap底层是哈希表，导包

        Set<String> set = new TreeSet<>();
        Set<String> set2 = new HashSet<>();

    }

    public static void main1(String[] args) {
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        int[] arr = {82,56,62,88,90,36};
        int[] arr1 = {80,30,48,60,90,56};
        for (int i = 0; i < arr.length; i++) {
            binarySearchTree.insert(arr1[i]); // 插入数据后就会形成一棵二叉搜索树了
        }
        System.out.println("===");

        binarySearchTree.remove(30);
        binarySearchTree.remove(80);
        binarySearchTree.inorder(binarySearchTree.root);

    }


}
